#include <iostream>
#include <cstdlib>

//欧几里德算法，O(lgn)，取模运算开销太大
long gcd1(long m, long n) {
    while (n != 0) {
        long rem = m%n;
        m = n;
        n = rem;
    }
    return m;
}

//欧几里德算法，递归实现，O(lgn)，当整数很大时，取模运算开销太大
long gcd2(long m, long n) {
    return (!n)?m:gcd2(n, m%n);
}

//判断偶数
bool isEven(long m) {
    return ((((char)m)&0x01)!=0x01);
}

//分治算法，O(lgn)，利用移位操作代替取模运算
long gcd3(long m, long n) {
    if (m < n) {
        return gcd3(n, m);
    }
    if (n == 0){
        return m;
    } else {
        if (isEven(m)) {
            if (isEven(n)) {
                //m,n都是偶数
                return (gcd3(m>>1, n>>1)<<1);
            } else {
                //m是偶数，n是奇数
                return gcd3(m>>1, n);
            }
        } else {
            if (isEven(n)) {
                //m是奇数，n是偶数
                return gcd3(m, n>>1);
            } else {
                //m,n都是奇数
                return gcd3(n, m-n);
            }
        }
    }
}

int main(void) {
    std::cout << "m=57, n = 14" << std::endl;
    std::cout << "gcd1(57, 14) : " << gcd1(57L, 14L) << std::endl;
    std::cout << "gcd2(57, 14) : " << gcd2(57L, 14L) << std::endl;
    std::cout << "gcd3(57, 14) : " << gcd3(56L, 14L) << std::endl;

    system("pause");
}
